package com.mdnote.practice.binary_search;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/18
 * @description 搜索旋转排序数组
 */
public class LeetCode33 {

    public static void main(String[] args) {
        LeetCode33 leetCode33 = new LeetCode33();
        int search = leetCode33.search(new int[]{6, 9}, 9);
        System.out.println(search);
    }

    public int search(int[] nums, int target) {

        if (nums.length == 0) {
            return -1;
        }
        return binarySearch(nums, target);
    }

    private int binarySearch(int[] nums, int target) {

        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            }

            // 看看哪边是有序的先
            // 等号是为了处理这种情况 {6， 9} target = 9，这是求得，mid 为 6，要让他走去右边
            if (nums[left] < nums[mid]) {
                // 左边有序，判断在不在范围里
                if (nums[left] <= target && nums[mid] >= target) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                // 右边有序，判断在不在范围里
                if (nums[mid] <= target && nums[right] >= target) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}
